//
// Created by DengLibin on 2019/1/28 0028.
//
#include <stdio.h>
#include <stdlib.h>
/**贪心算法
又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，
选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关
 * 求442元人民币至少需要多少张纸币，各种面值多少张*/
//人民币面值集合
static int values[] = {1, 2, 5, 10, 20, 50, 100};
static int haveNums[] = {3, 1, 2, 1, 1, 3, 5}; //各面值有多少张
static int nums[7] = {0}; //各面值需要多少张
//求较小值
static int minValue(int x, int y){
    return x < y ? x : y;
}
//根据金额求各个面值纸币的张数
static void change(int money){

    int num = 0; //当前面值多少张
    int leftMoney = money; //余多少钱
    //从最大的面值开始算
    for(int i = sizeof(values)/ sizeof(int)-1; i >= 0 ; i--){
        num = leftMoney / values[i];
        nums[i] = minValue(num, haveNums[i]);
        leftMoney = leftMoney - num * values[i];
    }
}


int main1(){
    change(442);
    int sum = 0;
    for(int i = 0; i < sizeof(nums)/ sizeof(int); i++){
        sum += values[i] * nums[i];
        printf("%d 元 %d 张\n", values[i], nums[i]);
    }
    printf("总额 %d 元\n",sum);
    return 0;
}
